package leetcode.string;

/**
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * <p>
 * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution28 {
    /**
     * 暴力解法 循环 在第一个找长度为n的needle串  被匹配串 要从匹配串的长度开始匹配,到匹配串的长度结束 视为有效 .. 即 haystack 串中所有长度为needle的长度的字串
     * 在匹配串中我们要找到 被匹配串的第 j+k 位置的元素 ==  匹配串的第k 元素 即可以继续向下匹配
     * 如果不行就说明被匹配串的第j个位置开始找不到匹配的串  设置flag标记为false ,此时j++ 移动一位继续找,
     * <p>
     * 时间复杂度 O(N x M) 空间复杂度 O(1)
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        if (needle == null || "".equals(needle)) {
            return 0;
        }
        int n = haystack.length(), m = needle.length();
        // 外层的 被匹配串遍历
        for (int j = 0; j + m <= n; j++) {
            boolean flag = true;
            for (int k = 0; k < m; k++) {
                if (haystack.charAt(j + k) != needle.charAt(k)) {
                    flag = false;
                    // 此时说明 j 开头的没找到匹配的
                    break;
                }
            }
            if (flag) {
                return j;
            }
        }
        return -1;
    }
}
